home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / prolog / brklyprl.lha / Emulator / hash_table.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-04-14  |  3.3 KB  |  175 lines
  1.  
  2. /* Copyright (C) 1988, 1989 Herve' Touati, Aquarius Project, UC Berkeley */
  3.  
  4. /* Copyright Herve' Touati, Aquarius Project, UC Berkeley */
  5.  
  6. #include <stream.h>
  7. #include "hash_table.h"
  8.  
  9. static unsigned simple_hash(int i) {return (unsigned) i;}
  10. static unsigned simple_equal(int i, int j) {return (i == j);}
  11.  
  12. void HashTable::allocate()
  13. {
  14.   char* malloc(int);
  15.   int object_size = sizeof(HashTableEntry*) + sizeof(HashTableEntry);
  16.   alloc_area = malloc(size * object_size);
  17.   if (alloc_area == 0) {
  18.     cerr << "Can't allocate this hash table\n";
  19.     exit(1);
  20.   }
  21.   table = (HashTableEntry**) alloc_area;
  22.   next_entry = (HashTableEntry*) (table + size);
  23.   next_entry0 = next_entry + size;
  24.   clear();
  25. }
  26.  
  27. void HashTable::reenter_old_data(int old_size, HashTableEntry** old_table)
  28. {
  29.   register HashTableEntry** c;
  30.   for (int i = 0; i < old_size; i++) {
  31.     c = &old_table[i];
  32.     while (*c != 0) {
  33.       bind((*c)->key, (*c)->value);
  34.       c = &((*c)->next);
  35.     }
  36.   }
  37. }
  38.  
  39. void HashTable::rehash()
  40. {
  41.   void free(char*);
  42.   char* old_alloc_area = alloc_area;
  43.   HashTableEntry** old_table = table;
  44.   int old_size = size;
  45.   size <<= 1;
  46.   allocate();
  47.   reenter_old_data(old_size, old_table);
  48.   free(old_alloc_area);
  49. }
  50.  
  51. HashTable::HashTable(int SIZE)
  52. {
  53.   size = SIZE;
  54.   allocate();
  55. }
  56.  
  57. HashTableEntry** HashTable::get_cell(int n) 
  58. {
  59.   HashTableEntry** c = &table[(unsigned) n % size];
  60.   while (*c != 0 && (*c)->key != n)
  61.     c = &((*c)->next);
  62.   return c;
  63. }
  64.  
  65. void HashTable::bind(int n1, int n2) 
  66. {
  67.   HashTableEntry** c = get_cell(n1);
  68.   if (*c == 0) {
  69.     if ((*c = new_cell()) == 0) {
  70.       rehash();
  71.       bind(n1, n2);
  72.       return;
  73.     }
  74.     (*c)->next = 0;
  75.     (*c)->key = n1;
  76.   }
  77.   (*c)->value = n2;
  78. }
  79.  
  80. int HashTable::get(int n) 
  81. {
  82.   HashTableEntry** c = get_cell(n);
  83.   if (*c == 0) {
  84.     status = HASH_MISS;
  85.     return 0;
  86.   } else {
  87.     status = HASH_HIT;
  88.     return (*c)->value;
  89.   }
  90. }
  91.  
  92. void HashTable::clear()
  93. {
  94.   register HashTableEntry** c = table;
  95.   register HashTableEntry** c0 = table + size;
  96.   for (; c < c0; c++) 
  97.     *c = 0;
  98.   next_entry = (HashTableEntry*) (table + size);
  99. }
  100.  
  101. void HashTable::reset()
  102. {
  103.   for (int i = 0; i < size; i++)
  104.     if (table[i] != 0) {
  105.       next_cell = &table[i];
  106.       next_index = i;
  107.       return;
  108.     };
  109.   next_cell = 0;
  110.   next_index = size;
  111. }
  112.  
  113. HashTableEntry* HashTable::next()
  114. {
  115.   HashTableEntry* result;
  116.   if (next_index == size)
  117.     return 0;
  118.   result = *next_cell;
  119.   next_cell = &((*next_cell)->next);
  120.   if (*next_cell != 0)
  121.     return result;
  122.   next_index++;
  123.   for (int i = next_index; i < size; i++)
  124.     if (table[i] != 0) {
  125.       next_cell = &table[i];
  126.       next_index = i;
  127.       return result;
  128.     };
  129.   next_cell = 0;
  130.   next_index = size;
  131.   return result;
  132. }  
  133.  
  134. void HashTable::print()
  135. {
  136.   reset();
  137.   HashTableEntry* e;
  138.   while (e = next())
  139.     e->print();
  140. }
  141.  
  142. #ifdef DEBUG_HASH_TABLE
  143.  
  144. void out_of_store()
  145. {
  146.   cerr << "operator new failed: out of store\n";
  147.   exit(1);
  148. }
  149. typedef void (*PF)();
  150.  
  151. extern PF set_new_handler(PF);
  152.  
  153. main() {
  154.   int i1, i2;
  155.   HashTable T;
  156.   set_new_handler(&out_of_store);
  157.   cout << "Try out hash tables \n";
  158.   for (;;) {
  159.     cin >> i1 >> i2;
  160.     if (cin.rdstate() != _good)
  161.       break;
  162.     T.bind(i1, i2);
  163.     cin >> i1;
  164.     cout << T.get(i1) << "\n";
  165.   }
  166.   T.print();
  167.   cout << "clear\n";
  168.   T.clear();
  169.   T.print();
  170.   cout << "add one\n";
  171.   T.bind(12,23);
  172.   T.print();
  173. }
  174. #endif
  175.